#include <stdio.h>
#include <stdlib.h>  
#include <math.h>
#include "projet.h"
#include "parser.h"
#include "algo1.h"
#include "cycle3.h"
#include "cycle4.h"
#include "cycle5.h"


int appartient_cycle_5(int** liens,int nb_terminaux,int i,int j){
  if((appartient_cycle_3(liens,nb_terminaux,i,j)==1)||appartient_cycle_4(liens,nb_terminaux,i,j)==1)
    return 1;
  else{
    int n;
    int k;
    int l;
    for(k=0;k<nb_terminaux;k++)
      for(n=0;n<nb_terminaux;n++)
	for(l=0;l<nb_terminaux;l++)
	  if(k!=i&&k!=j&&n!=i&&n!=j&&l!=i&&l!=j&&liens[i][n]==1&&liens[j][k]==1&&liens[k][l]==1&&liens[l][n]==1)
	    return 1;
    return 0;
  }   
}



int verifie_cycle_5(int** liens,int nb_terminaux){
  int i;
  int j;
  int d[nb_terminaux];
  int pere[nb_terminaux]; 
  for(i=0;i<nb_terminaux;i++)
    for(j=0;j<nb_terminaux;j++)
      if(liens[i][j]==1&&appartient_cycle_5(liens,nb_terminaux,i,j)!=1)
	return 0;
  return 1;
}


void relier_sommet_5(int** liens,int** distances,int nb_terminaux,int a,int b){
  int i;
  int j;
  int k;
  int imin=-1;
  int jmin;
  int min=-1;
  for(j=0;j<nb_terminaux;j++)
    if(liens[j][b]==1&&j!=a&&j!=b)
      for(i=0;i<nb_terminaux;i++)
	if(liens[i][a]==1&&i!=a&&i!=b)
	  for(k=0;k<nb_terminaux;k++)
	    if(k!=a&&k!=b&&k!=i&&k!=j){
	      if(liens[j][k]==1&&(min==-1||distances[k][i]<min)){
		min=distances[k][i];
		imin=i;
		jmin=k;
	      }
	      if(liens[i][k]==1&&(min==-1||distances[k][j]<min)){
		min=distances[k][j];
		imin=k;
		jmin=j;
	      }
	    }
  if(imin == -1){
    for(j=0;j<nb_terminaux;j++)
      if(j!=b&&j!=a&&liens[b][j]==1){
	imin=a;
	jmin=j;
      }
    for(j=0;j<nb_terminaux;j++)
      if(j!=b&&j!=a&&liens[a][j]==1){
	imin=b;
	jmin=j;
      }
  }
  liens[imin][jmin]=1;
  liens[jmin][imin]=1;
} 

void creation_des_cycles_5(int** liens,int** distances,int nb_terminaux){
  int i;
  int j;
  int k;
  for(i=0;i<nb_terminaux;i++)
    for(j=0;j<nb_terminaux;j++)
      if(liens[i][j]==1&&appartient_cycle_5(liens,nb_terminaux,i,j)==0)
	relier_sommet_5(liens,distances,nb_terminaux,i,j);
}	
